#include <iostream>

using namespace std;

const int k = 100;
int y[k],x1[k],x2[k],ans[k];
int n;
int count = 0;

void pt(){
	for(int i = 0; i < n; i++){
		cout << ans[i] << ' ';
	}
	cout << endl;
}

void backtrack(int step){
	
	if(step > n){
		count++;
		if(count <= 3){
			pt();
		}
		return;
	}
	
	for(int i = 0; i < n;i++){
		if((!y[i]) && (!x1[i+step]) && (!x2[i-step+n])){
			y[i] = 1;
			x1[i+step] = 1;
			x2[i-step+n] = 1;
			ans[step-1] = i+1;
			
			backtrack(step+1);
			
			y[i] = 0;
			x1[i+step] = 0;
			x2[i-step+n] = 0;
			ans[step-1] = 0;
		}
	}
	
}

int main(){
	
	cin >> n;
	
	backtrack(1);
	
	cout << count;
	
	return 0;
}
